package demo;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
    private  boolean isMatch(char left,char right){
        if(left=='('){
            return right==')';
        }
        if(left=='['){
            return right==']';
        }

        return right=='}';
    }
    public boolean isValid(String s) {
        Deque<Character> stack=new LinkedList<>();
        char[]array=s.toCharArray();
        for(char ch:array){
            if(ch=='('||ch=='['||ch=='{'){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char left=stack.pop();
                if(!isMatch(left,ch)){
                    return false;
                }
            }

        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }
}